package main;

import java.util.Collections;

public class saveWorld {
	

	public static void main(String argv[]) {
		/**
		 * Algoritmo genetico final
		 */
		//tempo de inicio da execucao
		Long inicio = System.currentTimeMillis();

		
		/*
		*Parametros:
		*/
		//limite de individuos que passa proxima geracao
		int nIndividuos=50;
		//percentual de individuos a ser cruzado
		int pCruz = 25;
		//percentual de individuos a passar por mutacao
		int pMuta = 50;
		//probabilidade de adicionar estacao a individuo na mutacao
		double pAdd = 0.2;
		
		
		//inicializa auxiliares
		int iteracao = 0;
		Long total, lin, lout, tmutin1, tmutout1, tmutin2, tmutout2, tcruzin, tcruzout,
		tmedtot = new Long(0), tmedmut1 = new Long(0), tmedmut2 =  new Long(0), tmedcruz =  new Long(0);
		Populacao newPop;
		
		
		//comeca algoritimo de fato
		World world = new World("input_125.in");
		

		Populacao pop = new Populacao().primPop(world);
		
		pop.mataRepetidos(pop.individuos);
		
		Collections.sort(pop.individuos);
		
		Individuo solBoa = pop.individuos.get(0);
		
		//solBoa.printIndividuo();
		
		Individuo solucao = solBoa;
		
		
		Long fim = System.currentTimeMillis();
		
		
		total = fim - inicio;
		
		while(total <50000){
			
			lin =  System.currentTimeMillis();
			//System.out.println("Iteracao: " + iteracao+" pop.individuos.size()= "+pop.individuos.size());
			
			if(total + tmedmut1 > 49500)
				break;

			tmutin1 = System.currentTimeMillis();
			newPop = pop.mutacao(world, pMuta, pAdd);
			newPop.mataRepetidos(newPop.individuos);
			tmutout1 = System.currentTimeMillis();
			
			if(iteracao==1)
				tmedmut1 = tmutout1 - tmutin1;
			else if(iteracao >1)
				tmedmut1 = (((iteracao-1)*tmedmut1)+(tmutout1-tmutin1))/iteracao;
			
			if(total + tmedcruz > 49000)
				break;
			
			pop.individuos.addAll(newPop.individuos);

			tcruzin= System.currentTimeMillis();
			newPop=pop.cruzamento(world, pCruz);
			newPop.mataRepetidos(newPop.individuos);
			tcruzout= System.currentTimeMillis();
		
			if(iteracao==1)
				tmedcruz= tcruzout- tcruzin;
			else if(iteracao >1)
				tmedcruz= (((iteracao-1)*tmedcruz)+(tcruzout- tcruzin))/iteracao;
			
			if(total + tmedmut2 > 48500)
				break;
			
			tmutin2 = System.currentTimeMillis();
			pop.individuos.addAll(newPop.individuos);
			pop.mataRepetidos(pop.individuos);
			Collections.sort(pop.individuos);
			
			//muta melhor individuo, se ele se tornar ainda melhor
			//substituira o antigo nova populacao
			pop.mutacaoMelhor(world);
			tmutout2 = System.currentTimeMillis();
			
			if(iteracao==1)
				tmedmut2= tmutout2- tmutin2;
			else if(iteracao >1)
				tmedmut2= (((iteracao-1)*tmedmut2)+(tmutout2- tmutin2))/iteracao;
			
			fim = System.currentTimeMillis();
			
			if(pop.individuos.size()>nIndividuos)
				pop.individuos=pop.individuos.subList(0, nIndividuos);
		
			solucao = pop.individuos.get(0);
			if(solucao.custo <= solBoa.custo)
				solBoa = solucao;
			//solBoa.printIndividuo();
		
			iteracao++;
			fim = System.currentTimeMillis();
			total = fim - inicio;
			//System.out.println("Tempo gasto: " + total + "ms");			
			lout = System.currentTimeMillis();
			if(total + tmedtot > 48000)
				break;
			
			if(iteracao==1)
				tmedtot = lout-lin;
			else
				tmedtot = (((iteracao-1)*tmedtot)+(lout-lin))/iteracao;
		}
		
		//impreime saida
		System.out.println("Valor: "+ solBoa.getCusto());
		System.out.println("Total: "+ solBoa.trueStations.size());
		for(int i=0;i<solBoa.trueStations.size();i++){
			System.out.println(world.getEstacoes().get(solBoa.trueStations.get(i)).getNome());
		}
		
		
		fim = System.currentTimeMillis();
	//	solBoa.printIndividuo();
		//System.out.println("ACABOU! Tempo gasto: " + (fim-inicio)/1000. + "s");
		
		//System.out.print((fim-inicio)/1000. + "s ");
		//solBoa.printIndividuo2();
	}
}
